/*
    最长递增子序列问题与扩展

    前置知识: 
    讲解006 - 二分搜索
    讲解066 - 一维动态规划
    【必备】课程的动态规划大专题从讲解066开始，建议从头开始学习会比较系统

    本节课讲述：最长递增子序列 & 最长不下降子序列 的最优解，以及一些扩展题目

    注意：
    本节课讲述的是最优解，时间复杂度是O(n*logn)，空间复杂度O(n)，好实现、理解难度不大
    这个问题也可以用线段树来求解，时间和空间复杂度和本节讲的最优解没有区别，但需要理解线段树
    线段树会在【扩展】课程阶段讲述

    ================================================

    题目1
    最长递增子序列
    给定一个整数数组nums
    找到其中最长严格递增子序列长度、最长不下降子序列长度
    测试链接 : https://leetcode.cn/problems/longest-increasing-subsequence/

    最长不下降子序列
    只需要改写二分策略即可

    ================================================

    题目2
    俄罗斯套娃信封问题
    给你一个二维整数数组envelopes
    其中envelopes[i]=[wi, hi]
    表示第 i 个信封的宽度和高度
    当另一个信封的宽度和高度都比这个信封大的时候
    这个信封就可以放进另一个信封里，如同俄罗斯套娃一样
    请计算 最多能有多少个信封能组成一组“俄罗斯套娃”信封
    即可以把一个信封放到另一个信封里面，注意不允许旋转信封
    测试链接 : https://leetcode.cn/problems/russian-doll-envelopes/

    ================================================

    题目3
    使数组K递增的最少操作次数
    给你一个下标从0开始包含n个正整数的数组arr，和一个正整数k
    如果对于每个满足 k <= i <= n-1 的下标 i
    都有 arr[i-k] <= arr[i] ，那么称 arr 是K递增的
    每一次操作中，你可以选择一个下标i并将arr[i]改成任意正整数
    请你返回对于给定的 k ，使数组变成K递增的最少操作次数
    测试链接 : 
    https://leetcode.cn/problems/minimum-operations-to-make-the-array-k-increasing/

    ================================================

    题目4
    最长数对链
    给你一个由n个数对组成的数对数组pairs
    其中 pairs[i] = [lefti, righti] 且 lefti < righti
    现在，我们定义一种 跟随 关系，当且仅当 b < c 时
    数对 p2 = [c, d] 才可以跟在 p1 = [a, b] 后面
    我们用这种形式来构造 数对链
    找出并返回能够形成的最长数对链的长度
    测试链接 : https://leetcode.cn/problems/maximum-length-of-pair-chain/

    ================================================

    题目5
    有一次修改机会的最长不下降子序列
    给定一个长度为n的数组arr，和一个整数k
    只有一次机会可以将其中连续的k个数全修改成任意一个值
    这次机会你可以用也可以不用，请返回最长不下降子序列长度
    1 <= k, n <= 10^5
    1 <= arr[i] <= 10^6
    测试链接 : https://www.luogu.com.cn/problem/P8776

    ================================================

    预告
    最长递增子序列的数量问题
    给定一个未排序的整数数组nums，返回最长递增子序列的个数
    测试链接 : 
    https://leetcode.cn/problems/number-of-longest-increasing-subsequence/

    这个问题的最优解能做到O(n * logn)
    会放在【扩展】课程阶段，详解树状数组(index tree)的时候来讲解
    用这个高级数据结构来求解这个题会很方便

    这里为什么要提呢？主要是想说：巧妙构思 vs 成熟体系

*/